//给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的
//句子。 
//
// 说明： 
//
// 
// 分隔时可以重复使用字典中的单词。 
// 你可以假设字典中没有重复的单词。 
// 
//
// 示例 1： 
//
// 输入:
//s = "catsanddog"
//wordDict = ["cat", "cats", "and", "sand", "dog"]
//输出:
//[
//  "cats and dog",
//  "cat sand dog"
//]
// 
//
// 示例 2： 
//
// 输入:
//s = "pineapplepenapple"
//wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
//输出:
//[
//  "pine apple pen apple",
//  "pineapple pen apple",
//  "pine applepen apple"
//]
//解释: 注意你可以重复使用字典中的单词。
// 
//
// 示例 3： 
//
// 输入:
//s = "catsandog"
//wordDict = ["cats", "dog", "sand", "and", "cat"]
//输出:
//[]
// 
// Related Topics 字典树 记忆化搜索 哈希表 字符串 动态规划 回溯 
// 👍 479 👎 0

/**
 * @author DaHuangXiao
 */
package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

public class WordBreakIi {
    public static void main(String[] args) {
        Solution solution = new WordBreakIi().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        private List<String> res = new ArrayList<>();

        public List<String> wordBreak(String s, List<String> wordDict) {
            dfs(s, wordDict, 0, s.length(), "");
            return res;
        }

        private void dfs(String s, List<String> wordDict, int start, int end, String path) {
            if (start > end) {
                return;
            }
            if (start == end) {
                res.add(path.substring(1,path.length()));
                return;
            }


            for (String word : wordDict) {
                if (start+word.length()<=end && word.equals(s.substring(start,start+word.length()))) {
                    dfs(s, wordDict, start+word.length(), end, path + " " + word);
                }
            }

        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}